package Practice;

import org.w3c.dom.ls.LSException;

import java.util.LinkedList;
import java.util.List;

public class Test {

    //移除链表元素  https://leetcode.cn/problems/remove-linked-list-elements/description/
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //上述操作没有处理头节点，需要额外处理
        if(head.val == val) {
            head = head.next;
            return head;
        }
        return head;
    }

    //反转链表  https://leetcode.cn/problems/reverse-linked-list/description/
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        ListNode curN = cur.next;
        //当链表反转结束后，一开始的head.next域就是最后一个节点的next域，需要置为null
        head.next = null;
        while (cur != null) {
            curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }

    //链表的中间节点  https://leetcode.cn/problems/middle-of-the-linked-list/description/
    public ListNode middleNode(ListNode head) {
        //不使用遍历链表取中间值计算，使用双指针计算
        if(head == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        //必须得fast != null在前，避免发生短路求值
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode middleNode1(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        int sum = 0;
        while (cur != null) {
            sum++;
            cur = cur.next;
        }
        int len = sum / 2;
        while (len != 0) {
            head = head.next;
            len--;
        }
        return head;
    }

    //链表中倒数K个节点  https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=13&tqId=11167&ru=/exam/oj
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead == null) {
            return pHead;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        int count = 0;
        while (pHead != null) {
            count++;
            pHead = pHead.next;
        }
        if (count < k) {
            return null;
        }
        while (k != 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //合并两个有序链表  https://leetcode.cn/problems/merge-two-sorted-lists/description/
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //没有必要
        /*if (list1 == null && list2 == null) {
            return list1;
        } else if (list1 == null && list2 != null) {
            return list2;
        }else if (list1 != null && list2 == null) {
            return list1;
        }*/

        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        /*if(list1 == null) {
            cur.next = list2;
        }
        if (list2 == null) {
            cur.next = list1;
        }*/
        //优化
        cur.next = list1 == null? list2:list1;
        return newHead.next;
    }

    //链表分割  https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode s1 = new ListNode();
        ListNode curS1 = s1;
        ListNode s2 = new ListNode();
        ListNode curS2 = s2;
        while (pHead != null) {
            if (pHead.val < x) {
                curS1.next = pHead;
                curS1 = curS1.next;
            }else {
                curS2.next = pHead;
                curS2 = curS2.next;
            }
            pHead = pHead.next;
        }
        //单向链表的最后一个next是null
        curS2.next = null;
        //假设没有小于x的数，则需要对s1中的next域进行判定，没有返回s2.next
        if (s1.next == null) {
            return s2.next;
        }
        curS1.next = s2.next;
        return s1.next;
    }

    //链表的回文结构  https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
    public boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null) {
            return true;
        }
        ListNode fast = A;
        ListNode slow = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }//此时slow是中间节点


        ListNode cur = slow.next;
        ListNode curN = null;
        while (cur != null) {
            curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        //此时slow是尾节点
        while (A != slow && A.next != slow) {
            if (A.val != slow.val) {
                return false;
            }
            A = A.next;
            slow = slow.next;
        }

        return true;
    }

    //相交链表  https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode aL = headA;
        ListNode bS = headB;
        int Long = 0;
        int Short = 0;
        while (aL.next != null) {
            Long++;
            aL = aL.next;
        }
        while (bS.next != null) {
            Short++;
            bS = bS.next;
        }
        /*if (countA > countB) {
            int len = countA - countB;
            while (len != 0) {
                headA = headA.next;
                len--;
            }
        }else {
            int len = countB - countA;
            while (len != 0) {
                headB = headB.next;
                len--;
            }
        }*/
        aL = headA;
        bS = headB;

        //优化：只看长链表，若当前aL中不是长链表那就进行更换，只确保当前aL链表是长链表
        int len = Long - Short;
        if(len < 0) {
            ListNode tmp = aL;
            aL = bS;
            bS = tmp;
            len = -len;
        }
        while (len != 0) {
            aL = aL.next;
        }
        while (aL != bS) {
            aL = aL.next;
            bS = bS.next;
        }
        if (aL == null) {
            return null;
        }
        return aL;
    }

    public static void main(String[] args) {
        LinkedList<LinkedList<Integer>> linkedLists = new LinkedList<>();
        linkedLists.add(new LinkedList<Integer>(List.of(1)));
        linkedLists.add(new LinkedList<Integer>(List.of(2)));
        linkedLists.add(new LinkedList<Integer>(List.of(3)));
        linkedLists.add(new LinkedList<Integer>(List.of(3)));
        linkedLists.add(new LinkedList<Integer>(List.of(1)));

    }
}
